home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / PLANAR_MAP.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  5.0 KB  |  125 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.3 Planar Maps (planar\_map)}
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $M$ of the data type $planar\_map$ is the combinatorial
  8. embedding of a planar graph.
  9.  
  10. \def\name{$planar\_map$}
  11. \def\type{planar\_map}
  12.  
  13. \bigskip
  14. {\bf 2. Creation}
  15.  
  16. \create M (graph\ G)
  17.  
  18. creates an instance $M$ of type $planar\_map$ and initializes it to 
  19. the planar map represented by the directed graph $G$. \precond $G$ 
  20. represents an undirected planar map, i.e. for every edge $(v,w)$ in $G$
  21. the reverse edge $(w,v)$ is also in $G$ and there is a planar embedding
  22. of $G$ such that for every node $v$ the ordering of the edges in the 
  23. adjacency list of $v$ corresponds to the counter-clockwise ordering of
  24. these edges around $v$ in the embedding. 
  25.  
  26.  
  27. \bigskip
  28. {\bf 3. Operations}
  29. \medskip
  30. Most operations are the same as for directed graphs. The following operations
  31. are either additional or have different effects.
  32. \medskip
  33. \+\cleartabs & \hskip 2truecm & \hskip 5.5truecm &\cr
  34. \+\op face       adj\_face  {edge\ e}
  35.                                {returns the face of \var\ to the right of $e$.}
  36. \smallskip
  37. \+\op list\<face\> all\_faces {}
  38.                                {returns the list of all faces of \var.}
  39. \smallskip
  40. \+\op list\<face\> adj\_faces {node\ v}
  41.                                {returns the list of all faces of \var\ adjacent}
  42. \+\nop                         {to node $v$ in counter-clockwise order.}
  43. \smallskip
  44. \+\op list\<edge\> adj\_edges {face\ f}
  45.                                {returns the list of all edges of \var\ bounding}
  46. \+\nop                         {face $f$ in clockwise order.}
  47. \smallskip
  48. \+\op list\<node\> adj\_nodes {face\ f}
  49.                                {returns the list of all nodes of \var\ adjacent}
  50. \+\nop                         {to face $f$ in clockwise order.}
  51. \smallskip
  52. \+\op edge       reverse   {edge\ e}
  53.                                  {returns the reversal of edge $e$ in \var. }
  54. \smallskip
  55. \+\op edge       first\_face\_edge {}
  56.                                  {returns the first edge of face $f$ in \var. }
  57. \smallskip
  58. \+\op edge       succ\_face\_edge {edge\ e}
  59.                                {returns the successor edge of $e$ in face $f$}
  60. \+\nop                         {i.e., the next edge in clockwise order.}
  61. \smallskip
  62. \+\op edge       pred\_face\_edge {edge\ e}
  63.                               {returns the predecessor edge of $e$ in face $f$,}
  64. \+\nop                        {i.e., the next edge in counter-clockwise order.}
  65. \smallskip
  66. \+\op edge new\_edge {edge\ e_1,\ edge\ e_2} {}
  67. \+\nop                        {inserts the edge $e=(source(e_1),source(e_2))$}
  68. \+\nop                        {and its reversal edge into $M$. \precond }
  69. \+\nop                        {$e_1$ and $e_2$ are bounding the same face $F$.}
  70. \+\nop                        {The operation splits $F$ into two new faces.}
  71. \smallskip
  72. \+\op edge del\_edge {edge\ e}
  73.                               {deletes the edge $e$ from \var. The two faces}
  74. \+\nop                        {adjacent to $e$ are united to one face.}
  75. \smallskip
  76. \+\op edge split\_edge {edge\ e}
  77.                             {splits edge $e=(v,w)$ and its reversal $r=(w,v)$}
  78. \+\nop                      {into edges $(v,u)$, $(u,w)$, $(w,u)$, and $(u,v)$.}
  79. \+\nop                      {Returns the edge $(u,w)$. }
  80. \smallskip
  81. \+\op node new\_node {face\ f}
  82.                            {splits face $f$ into triangles by inserting a new}
  83. \+\nop                     {node $u$ and connecting it to all nodes of $f$. }
  84. \+\nop                     {Returns $u$.}
  85. \smallskip
  86. \+\op node new\_node {list\<edge\>\ el}
  87.                            {splits the face bounded by the edges in $el$ by}
  88. \+\nop                     {inserting a new node $u$ and connecting it to all}
  89. \+\nop                     {source nodes of edges in $el$. \precond}
  90. \+\nop                     {all edges in $el$ bound the same face.}
  91. \smallskip
  92. \+\op list\<edge\> triangulate {}
  93.                              {triangulates all faces of \var\ by inserting new}
  94. \+\nop                       {edges. The list of inserted edges is is returned.}
  95. \smallskip
  96. \+\op int straight\_line\_embedding {node\_array(int)\ xcoord,\ node\_array(int)\ ycoord} {}
  97. \+\nop                    {computes a straight line embedding for $M$ with}
  98. \+\nop                    {integer coordinates $xcoord[v]$, $ycoord[v])$ in the}
  99. \+\nop                    {range $0\dots 2(n-1)$ for every node $v$ of $M$,}
  100. \+\nop                    {and returns the maximal used coordinate. }
  101.  
  102.  
  103.  
  104. \bigskip
  105. {\bf 4. Iteration}
  106.  
  107. {\bf forall\_faces}($f,M$)  
  108. $\{$ ``the faces of $M$ are successively assigned to $f$" $\}$
  109.  
  110. {\bf forall\_adj\_edges}($e,f$) \nl
  111. \phantom{{\bf forall\_edges}($v,M$)}
  112. $\{$ ``the edges adjacent to face f are successively assigned to e" $\}$
  113.  
  114. \bigskip
  115. {\bf 5. Implementation}
  116.  
  117. Planar maps are implemented by parameterized directed graphs.
  118. All operations take constant time, except of, new\_edge and del\_edge
  119. which take time $O(f)$ where $f$ is the number of edges in the created
  120. faces, and triangulate and straight\_line\_embedding take time $O(n)$
  121. where $n$ is the current size (number of edges) of the planar map.
  122.  
  123. \vfill\eject
  124.  
  125.